UVa/11385 - Da Vinci Code/11385.2.cpp

   1 /*
   2   Problem: 11385 - Da Vinci Code
   3   Author: Andrés Mejía-Posada
   4
   5   Que gonorrea de problema.
   6  */
   7
   8 using namespace std;
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <string>
  12 #include <vector>
  13
  14 int fib[50], T, n;
  15 string ans, s;
  16
  17 int main(){
  18   fib[0] = 1, fib[1] = 2;
  19   for (int i=2; fib[i-1] + fib[i-2] > 0; ++i) fib[i] = fib[i-1] + fib[i-2];
  20
  21   for(cin >> T; T--; cout << ans << endl){
  22     cin >> n;
  23     vector<int> nums(n);
  24     for (int i=0; i<n; ++i) cin >> nums[i];
  25
  26     getline(cin, s), getline(cin, s);
  27     for (int i=0; i<s.size(); ++i) if (!isupper(s[i])) s.erase(i, 1), i--;
  28
  29     vector<int> pos(n);
  30     for (int i=0; i<n; ++i) pos[i] = lower_bound(fib, fib + 50, nums[i]) - fib;
  31
  32     ans = string(*max_element(pos.begin(), pos.end()) + 1, ' ');
  33
  34     for (int i=min(s.size(), pos.size()) - 1; i >= 0; --i) ans[pos[i]] = s[i];
  35   }
  36   return 0;
  37 }